package list

func ReverseKGroup(head *ListNode, k int) *ListNode {

	// 闭包函数 反转链表
	var reverselist func(head *ListNode) *ListNode
	reverselist = func(head *ListNode) *ListNode {
		if head == nil || head.Next == nil {
			return head
		}
		newHead := reverselist(head.Next)
		next := head.Next
		next.Next = head
		head.Next = nil
		return newHead
	}

	dummyHead := &ListNode{
		Val:  -1,
		Next: head,
	}
	temp := dummyHead

	for temp != nil {
		tail := temp
		head = temp.Next
		for i := 0; i < k && tail != nil; i++ {
			tail = tail.Next
		}
		if tail == nil {
			return dummyHead.Next
		}
		nextHead := tail.Next
		tail.Next = nil
		reverselist(temp.Next)
		temp.Next = tail
		head.Next = nextHead
		temp = head

	}
	return dummyHead.Next

}

func ReverseKGroup2(head *ListNode, k int) *ListNode {

	if head == nil {
		return nil
		// return
	}

	node_group := [][]*ListNode{}
	i := 0
	group := []*ListNode{}

	for temp := head; temp != nil; temp = temp.Next {
		group = append(group, temp)
		i++
		if i == k {
			node_group = append(node_group, group)
			i = 0
			group = []*ListNode{}
		}
	}

	if 0 < i && i < k {
		node_group = append(node_group, group) // 最后一组
	}

	group_num := len(node_group)
	for i := 0; i < group_num; i++ {
		if len(node_group[i]) < k {
			break
		}

		for j := k - 1; j > 0; j-- {
			node_group[i][j].Next = node_group[i][j-1]
		}

	}

	for i := 0; i < group_num-1; i++ {
		if len(node_group[i+1]) == k {
			node_group[i][0].Next = node_group[i+1][k-1]
		} else {
			node_group[i][0].Next = node_group[i+1][0]
		}
	}

	if len(node_group[group_num-1]) == k {
		node_group[group_num-1][0].Next = nil
	} else {
		node_group[group_num-1][len(node_group[group_num-1])-1].Next = nil
	}

	if len(node_group[0]) == k {
		return node_group[0][k-1]
	} else {
		return node_group[0][0]
	}

}
